package com.murphy.algorithm.linked;

import com.alibaba.fastjson.JSON;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * 最近未被使用淘汰算法
 * @author dongsufeng
 * @date 2020/9/4 15:54
 * @version 1.0
 */
public class LRU {
	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<>();
		MyLinkedList.Node<Integer> node =new MyLinkedList.Node(null,111,null);
		for (int i=0;i<20;i++){
			int num =(int) (Math.random()*20+1);
			myLinked(num, node);
			System.out.println(node.e);
		}
	}
	public static void fn(Integer item,LinkedList<Integer> list){
		if (list.contains(item)){
			list.remove(item);
			((LinkedList<Integer>) list).addFirst(item);
		}else {
			((LinkedList<Integer>) list).addFirst(item);
			if (list.size()>=10){
				((LinkedList<Integer>) list).removeLast();
			}
		}
	}

	/**
	 * 未实现-废品
	 * @param item
	 * @param node
	 * @return
	 */
	public static MyLinkedList.Node myLinked(Integer item, MyLinkedList.Node<Integer> node){
		MyLinkedList.Node<Integer> pre = null;
		MyLinkedList.Node<Integer> sys = null;
		boolean flag = false;
		MyLinkedList.Node<Integer> last = null;
		while (node!=null){
			if (node.e.intValue() == item){
				sys = node;
				node.pre.next = node.next;
				node.next.pre = node.pre;
				pre = node;
				sys.pre = null;
				sys.next = pre;
				node.pre = sys;
				flag = true;
				break;
			}else {
				if (node.next == null){
					last = node;
				}
				node = node.next;
			}
		}
		if (!flag){
			MyLinkedList.Node<Integer> newNode = new MyLinkedList.Node<>(last,item,null);
			if (last != null) {
				last.next = newNode;
				node = last;
			}else {
				return newNode;
			}
		}
		return node;
	}
}
